//
// Created by ASUS on 2025/4/6/星期日.
//
#include <bits/stdc++.h>
using namespace std;

#define int long long

class LCA{
private:
	vector<vector<int>> g,pa;
	vector<int> dep;
	int n,m;
public:
	LCA(vector<vector<int>>&g){
		this->g=g;
		n=g.size();
		m=__lg(n)+1;
		dep.resize(n);
		pa.resize(n,vector<int>(m));
		dfs(0,-1);
	}

	void dfs(int x,int fa){
		pa[x][0]=fa;
		dep[x]=dep[fa]+1;
		for(int i=1;i<m;i++){
			pa[x][i]=pa[pa[x][i-1]][i-1];
		}
		for(int y:g[x]){
			if(y!=fa){
				dfs(y,x);
			}
		}
	};

	int get_lca(int x,int y){
		if(dep[x]>dep[y]) swap(x,y);
		for(int i=m-1;i>=0;i--){
			if(dep[pa[y][i]]>=dep[x]){
				y=pa[y][i];
			}
		}
		if(x==y) return x;
		for(int i=m-1;i>=0;i--){
			int fx=pa[x][i],fy=pa[y][i];
			if(fx!=fy){
				x=fx;
				y=fy;
			}
		}
		return pa[x][0];
	}
};
